P1896 [SCOI2005] 互不侵犯 题解

1. 题目大意

在 $N \times N$ 的棋盘里面放 $K$ 个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共 $8$ 个格子。

注意是8个方向。

对于全部数据，$1 \le N \le 9$，$0 \le K \le N\times N$。

从这个数据范围看出是状压动规，暴搜明显超时。

2. 思路分析

现在知道是状压动规，考虑如何建立状态、转移方程、边界。

• 状态

  首先，$1 \le N \le 9$，可以想到用一个长 $9$ 位的二进制串来表示状态。

  思考一下转移必须的条件，可以把每一行作为一个阶段（于是有了第一维），还需要知道这一行的选取情况（第二维），此外，还要知道已经用掉的国王数量（第三维）。

  于是有了具体的状态定义：令 dp[i][j][k] 表示第 $i$ 行，使用 $j$ 的方法安放，已经用了 $k$ 个国王。

  为了方便后续的判断，也节省时间，可以把一行中所有合法的状态全部处理出来，存入数组中。

• 转移方程

  明显，要从第 $i-1$ 个状态转移过来。

  枚举所有的当前状态和上一个状态，再枚举已经用去的国王数，把符合条件的累加起来。得到转移方程：

  $$
  dp_{i,now,k}=\sum dp_{i-1,lst,k-v}\
  \
  (v是now状态所用去的国王数量)
  $$

  基本完成，还有一个小问题——怎么判断两行状态是否合法？

  • 上下

    很好处理，把两个状态取 $&$ ，如果答案不等于0，说明不可行。如图：
    

  • 对角

    考虑把一个状态左移一个，就转化为了上下的情况。如图：
    

  于是有了上下和对角的判断函数：

  1 2 3 4 5 6

  //x,y是相邻两行的状态 bool check(int x,int y){ if((x&y)||((x<<1)&y)||(x&(y<<1))) return false; return true; }

  • 左右

    上面提到可以通过预处理确定一行中左右的合法情况，这里具体说明：直接用 dfs 预处理可以的情况，写法如下：

    1 2 3 4 5 6 7 8 9 10 11 12 13

    //d表示当前处理的列号，tot表示使用的国王总数，val表示建立起的状态二进制串 void init(int d,int tot,int val){ if(d>n){ num++; a[num]=val; v[num]=tot; return; } init(d+1,tot,val); //这一格空着 init(d+2,tot+1,val|(1<<(d-1))); //这一格填上，直接通过+2跳过下一个，避免相邻 }

• 边界

  明显，第一行所有状态都是 $1$。

• 答案

  易得：

  $$
  ans=\sum dp_{n,i,k}
  \
  (i遍历所有状态)
  $$

3. 注意事项

1. 会爆 int，要开long long！
2. 注意位运算优先级，保险起见加上括号！

4. code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[2000],num;
int v[2000];
long long dp[20][2000][200];
void init(int d,int tot,int val){
    if(d>n){
        num++;
        a[num]=val;
        v[num]=tot;
        return;
    }
    init(d+1,tot,val);
    init(d+2,tot+1,val|(1<<(d-1)));
}
bool check(int x,int y){
    if((x&y)||((x<<1)&y)||(x&(y<<1)))
        return false;
    return true;
}
int main(){
    cin>>n>>k;
    init(1,0,0);
    for(int i=1;i<=num;i++)
        dp[1][i][v[i]]=1;
    for(int i=2;i<=n;i++)
        for(int now=1;now<=num;now++)
            for(int lst=1;lst<=num;lst++)
                if(check(a[lst],a[now]))
                    for(int sum=v[now];sum<=k;sum++)
                        dp[i][now][sum]+=dp[i-1][lst][sum-v[now]];
    long long ans=0;
    for(int i=0;i<=num;i++)
        ans+=dp[n][i][k];
    cout<<ans<<endl;
    return 0;
}